package leetcode.editor.cn1.study01;

public class ErWeiShuZuZhongDeChaZhaoLcof {
    public static void main(String[] args) {
        Solution solution = new ErWeiShuZuZhongDeChaZhaoLcof().new Solution();
        // TO TEST
        int[][] matrix = new int[][]{
                {1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        };
        System.out.println(solution.findNumberIn2DArray(matrix, 20));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean findNumberIn2DArray(int[][] matrix, int target) {
            // 行数
            int n = matrix.length;
            if (n == 0)
                return false;
            // 列数
            int m = matrix[0].length;
            if (m == 0)
                return false;
            int i = 0, j = m - 1;
            // i, j 在二维数组范围内
            while (i < n && j >= 0) {
                if (matrix[i][j] == target) {
                    return true;
                }
                if (matrix[i][j] > target) {
                    j--;
                    continue;
                }
                if (matrix[i][j] < target) {
                    i++;
                    continue;
                }
            }
            // 没有找到
            return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
